// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
)

// jumpSearch 使用跳转搜索算法在排序数组中执行给定键的搜索。
func jumpSearch(array []int, key int) int {
	// 通过取数组长度的平方根来确定块大小
	var blockSize = int(math.Sqrt(float64(len(array))))
	// 将搜索的起始索引初始化为零
	var i = 0
	// 继续循环直到当前块包含键，或者我们到达数组的末尾
	for {
		// 如果当前元素大于或等于键，则跳出循环
		if array[i] >= key {
			break
		}
		// 如果我们已经越过数组的末尾，则跳出循环
		if i > len(array) {
			break
		}
		// 否则，通过将块大小添加到当前索引来跳转到下一个块
		i += blockSize
	}
	// 从当前索引向后迭代以找到键的第一次出现
	for j := i; j > 0; j-- {
		// 如果当前元素与键匹配，则返回其索引
		if array[j] == key {
			return j
		}
	}
	// 如果未找到密钥，则返回 -1
	return -1
}

func main() {
	array := []int{1, 2, 6, 5, 88, 66, 77, 69, 76, 99}
	fmt.Println(jumpSearch(array, 77))
}

//$ go run jumpSearch.go
//6
